#include "bits/stdc++.h"

using namespace std;

const int N = 100010;

typedef long long LL;
typedef pair<LL, int> PLI;

int n, m;

int main() {
    cin >> n >> m;
    priority_queue<PLI, vector<PLI>, greater<PLI>> heap;//最小堆

    for (int i = 0; i < n; i++) {
        LL x;
        cin >> x;
        heap.push({x, 0});//将每种字符进最小堆
    }
    //构造k叉huffman树
    while ((n - 1) % (m - 1)) {
        heap.push({0ll, 0});
        n++;
    }
    LL res = 0;//保存WPL
    //堆中元素大于一，意思是最后归并成一个结点
    while (heap.size() > 1) {
        LL sum = 0;//记录编码长度
        int depth = 0;//初始化huffman树深度
        for (int i = 0; i < m; i++) {//找到k个最小的结点，进行归并
            sum += heap.top().first;//sum保存每个分支节点的重量
            depth = max(depth, heap.top().second);//深度等于0或者自身已保存深度
            heap.pop();//将k个结点出队
        }
        heap.push({sum, depth + 1});//将归并好的结点入队，并将其深度+1
        res += sum;//wps等于每个分支节点的重量和
    }
    //最长编码次数就是其深度，注意根节点深度为0
    cout << res << endl << heap.top().second << endl;
    return 0;
}
